#pragma once

#include <set>

class ASNode;
class ASPoly;
class ASNode;

typedef vector<ASNode*>				ASNodeList;
typedef vector<ASNode*>::iterator	ASNodeIterator;

class ASPoly
{
	vector<v3>		vertices;
	ASNodeList		neighbors;
public:
	v3				centroid;
	virtual	ASPoly*	getASPoly(){return this;}
};

class	ASNode : public Describable
{
public:
	v3				centroid;
	v3				normal;
	int				islandIndex;
	virtual	ASPoly*	getPoly(){return null;}
	ASNodeList		links;
	bool			visited;
	virtual void	getDescription(Dictionary&	dict);
	void	detach(ASNode*	from=null);
	void	linkTo(ASNode*	to);
	ASNode*	randomWalk(int	steps);
	ASNode();
	virtual ~ASNode();
};


class ASNodeVisitor
{
public:
	float			totalCost;
	float			costToTarget;
	float			costToStart;
	ASNodeVisitor*	parent;
	ASNode*			node;
	bool operator < (const ASNodeVisitor*& refParam) const
	{
		return (totalCost > (refParam->totalCost));
	}
};


struct predASVNode : binary_function <ASNodeVisitor*,ASNodeVisitor*,bool>
{
	bool	operator()(const ASNodeVisitor* a,const ASNodeVisitor* b)const
	{
		return (a->totalCost<b->totalCost);
	}
};


class	ASPathIterator : public pathIterator
{
public:
	Array<ASNode*>*	a;
	virtual	int	size(){return a->size();}
	virtual	v3&	get(int	index){return (*a)[index]->centroid;}
	ASPathIterator(Array<ASNode*>& _a){a=&_a;};
	virtual	~ASPathIterator(){};
};


typedef vector<ASNode*>									ASNodeList;
typedef vector<ASNode*>::iterator						ASNodeIterator;
typedef multiset<ASNodeVisitor*,predASVNode>			ASNodeSet;
typedef multiset<ASNodeVisitor*,predASVNode>::iterator	ASNodeSetIterator;
typedef map<ASNode*,ASNodeVisitor*>						ASNodeVisitorMap;

class	ASSearch
{
public:
	Pool<ASNodeVisitor,128*128>			visitorPool;
	ASNodeVisitorMap					closedMap;
	ASNodeVisitorMap					newMap;
	ASNodeVisitorMap					openMap;
	ASNodeSet							openSet;
	ASNodeSet							closedSet;
	list<ASNodeVisitor*>				newNodes;
	ASNodeVisitor*						firstVisitor;
public:
	ASNode*								target;
	list<ASNodeVisitor*>				path;
	bool								searching;
	void								pathToArray(Array<ASNode*>&	nar);
	f32									estimateCost(ASNode*	from,ASNode*	to);
	ASNodeVisitor*						visit(ASNode*	node,ASNode*	target,ASNodeVisitor*	parent);
	bool								expand();
	void								renderPath();
	bool								search();
	bool								find();
	void								startSearch(ASNode*	startNode,ASNode*	_target);
	ASSearch(ASNode*	startNode,ASNode*	_target);
	virtual ~ASSearch();
};

typedef list<ASSearch*>								ASSearchList;
typedef list<ASSearch*>::iterator					ASSearchIterator;

class	AITask	:	public RenderableTask
{
public:

	map<ASNode*,set<ASNode*>>	deadLinks;
	float			meshDensity;
	ASSearchList	activeSearches;
	ASNode*			root;
	BBox			bounds;
	ASNodeList		nodes;
	ASSearchList	searches;
	ASNodeList		visited;
	map<int,ASNodeList>	spatialHash;
	static	const int		xaxis=0;	//World east/west
	static	const int		yaxis=2;	//World north/south
	static	const int		zaxis=1;	//World up/down

	void			expandIndex(v3&	pos);
	ASNodeList&		indexLookup(v3&	pos);
	bool			linkIsDead(ASNode*	nn,ASNode*	n);

	ASNode*			getNode(int	index);
	ASNode*			getRandomNode();
	void			destroyLink(ASNode*	node1,ASNode*	node2);
	bool	isWater(ASNode*	a);
	bool	isShore(ASNode*	a,ASNode* b);
	const TCHAR		*typeName(void){return _T("AITask");};
	AITask(const char*	mapName,bool	deleteIslands=true,bool castSign=false,bool	checkObstructions=true);
	virtual ~AITask();
	ASNode*			findNearestNode(v3	pos,bool	collide);
	void			generateNavMesh(BBox&	worldBounds,bool castSign,bool	checkObstructions);
	void			findIslands(bool	deleteIslands=true);
	void			renderNavMesh();
	void			clearVisited();
	virtual	void	render();
	virtual	void	start();
	virtual	void	stop();
	virtual	void	run();
};